package Leetcode;


/**
 * 给你一个链表的头节点 head和一个特定值 x ，请你对链表进行分隔，使得所有小于x的节点都出现在大于或等于x的节点之前。
 */
public class test02_04fengeListCode {


    public ListNode partition(ListNode head, int x) {
        //判断链表是否为空
        if (head == null || head.next == null) {
            return head;
        }
        //简历两个新的链表，一个储存大于x的节点，一个存储小于x的节点
        ListNode bigHead = new ListNode();
        ListNode bigTail = bigHead;
        ListNode smallHead = new ListNode();
        ListNode smallTail = smallHead;
        while (head != null) {
            if (head.val < x) {
                smallTail.next = head;
                smallTail = head;
            } else {
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }

        bigTail.next=null;
        smallTail.next=bigHead.next;
        return smallHead.next;

    }
}
